package leetcode;

/**
 * 42.接雨水
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 * <p>
 * 方法一：动态规划
 * <p>
 * 方法二：双指针
 */
public class Trap {

    public static void main(String[] args) {
        int[] arr = {0, 1, 1, 3};
        trap(arr);
    }

    /**
     * 动态规划 推荐 Get
     *
     *
     * height[i] 表示柱子的高度
     * leftMax[i] 表示柱子i及其左边最大高度
     * rightMax[i] 表示柱子i及其右边最大高度
     * <p>
     * 公式为
     * leftMax[i] = Math.max(leftMax[i-1] , height[i])
     * rightMax[i] = Math.max(rightMax[i+1] , height[i])
     *
     * @param height
     * @return
     */
    public static int trap(int[] height) {

        int n = height.length;
        if (n == 0) {
            return 0;
        }

        int[] leftMax = new int[height.length];
        leftMax[0] = height[0];
        for (int i = 1; i < height.length; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }

        int[] rightMax = new int[height.length];
        rightMax[height.length - 1] = height[height.length - 1];
        for (int i = height.length - 1; i > 0; i--) {
            rightMax[i - 1] = Math.max(rightMax[i], height[i - 1]);
        }

        int result = 0;
        for (int i = 0; i < n; i++) {
            result += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return result;
    }


    /**
     * 双指针 理解起来跟DP难度差不多
     * 难又不难
     *
     * @param height
     * @return
     */
    public int trap1(int[] height) {
        int ans = 0;
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        while (left < right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            if (height[left] < height[right]) {
                ans = ans + (leftMax - height[left]);
                ++left;
            } else {
                ans = ans + (rightMax - height[right]);
                --right;
            }
        }
        return ans;
    }


    // 时间复杂度 有 n n2 m*n logn
    // 遍历两次即 2n 也属于 n级别
}
